1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=1e5+10,mod=1e9+7;
int n,m,pow[maxn],in[maxn];
int ecnt,head[maxn],to[maxn<<1],nxt[maxn<<1];
inline void addedge(int a,int b){
to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt,in[a]++ ;
to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt,in[b]++;
}
int bel[maxn],dfn[maxn],low[maxn],cut[maxn],cnt[maxn],cntbel[maxn],cutcnt[maxn];
bool col[maxn],unsol[maxn],unsolbel[maxn];
void tarjan(int x,int fa){
bel[x]=bel[0],cutcnt[x]=cnt[x]=col[x];
dfn[x]=low[x]=++dfn[0];
for(int u,i=head[x];i;i=nxt[i]) if((u=to[i])!=fa)
if(!dfn[u]) {
tarjan(u,x),low[x]=min(low[x],low[u]);
cnt[x]+=cnt[u];
if(dfn[x]<=low[u]) cutcnt[x]+=cnt[u],++cut[x],unsol[x]|=cnt[u]&1;
}else low[x]=min(low[x],dfn[u]);
cut[x]-=!fa;
}
inline void work(){
memset(head,0,sizeof head),ecnt=bel[0]=0;memset(dfn,0,sizeof dfn),memset(cut,0,sizeof cut),memset(in,0,sizeof in),memset(unsol,0,sizeof unsol);
n=read(),m=read();
for(int i=1;i<=m;i++) addedge(read(),read());
for(int c,i=1;i<=n;i++) scanf("%1d",&c),col[i]=c;
int cntunsol=0;
for(int i=1;i<=n;i++) if(!dfn[i])
bel[0]++,tarjan(i,0),cntunsol+=cnt[i]&1,cntbel[bel[0]]=cnt[i],unsolbel[bel[0]]=cntbel[bel[0]]&1;
int ans=m-n+bel[0];
printf("%d ",cntunsol?0:pow[ans]);
for(int i=1;i<=n;i++) {
if(!in[i]) printf("%d ",cntunsol^cnt[i]?0:pow[ans]);
else if(!cut[i]){
if((unsolbel[bel[i]] and !(cntunsol^col[i])) or (!unsolbel[bel[i]] and !cntunsol and !col[i]))
printf("%d ",pow[ans-in[i]+1+cut[i]]);
else printf("0 ");
}else if(!unsol[i] and !((cntbel[bel[i]]-cutcnt[i])&1) and !(cntunsol-unsolbel[bel[i]]))
printf("%d ",pow[ans-in[i]+1+cut[i]]);
else printf("0 ");
}
puts("");
}
}
signed main(){
star::pow[0]=1;
for(int i=1;i<=100000;i++) star::pow[i]=(star::pow[i-1]<<1)%star::mod;
int T=read();
while(T--)star::work();
return 0;
}
|
